Qué (quién) es recursion equations - definición

In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals ${\displaystyle \alpha }$. An admissible set is closed under ${\displaystyle \Sigma _{1}(L_{\alpha })}$ functions, where ${\displaystyle L_{\xi }}$ denotes a rank of Godel's constructible hierarchy. ${\displaystyle \alpha }$ is an admissible ordinal if ${\displaystyle L_{\alpha }}$ is a model of Kripke–Platek set theory. In what follows ${\displaystyle \alpha }$ is considered to be fixed.

The objects of study in ${\displaystyle \alpha }$ recursion are subsets of ${\displaystyle \alpha }$. These sets are said to have some properties:

• A set ${\displaystyle A\subseteq \alpha }$ is said to be ${\displaystyle \alpha }$-recursively-enumerable if it is ${\displaystyle \Sigma _{1}}$ definable over ${\displaystyle L_{\alpha }}$, possibly with parameters from ${\displaystyle L_{\alpha }}$ in the definition.
• A is ${\displaystyle \alpha }$-recursive if both A and ${\displaystyle \alpha \setminus A}$ (its relative complement in ${\displaystyle \alpha }$) are ${\displaystyle \alpha }$-recursively-enumerable. It's of note that ${\displaystyle \alpha }$-recursive sets are members of ${\displaystyle L_{\alpha +1}}$ by definition of ${\displaystyle L}$.
• Members of ${\displaystyle L_{\alpha }}$ are called ${\displaystyle \alpha }$-finite and play a similar role to the finite numbers in classical recursion theory.
• Members of ${\displaystyle L_{\alpha +1}}$ are called ${\displaystyle \alpha }$-arithmetic.

There are also some similar definitions for functions mapping ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$:

• A function mapping ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-recursively-enumerable, or ${\displaystyle \alpha }$-partial recursive, iff its graph is ${\displaystyle \Sigma _{1}}$-definable in ${\displaystyle (L_{\alpha },\in )}$.
• A function mapping ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-recursive iff its graph is ${\displaystyle \Delta _{1}}$-definable in ${\displaystyle (L_{\alpha },\in )}$.
• Additionally, a function mapping ${\displaystyle \alpha }$ to ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$-arithmetical iff there exists some ${\displaystyle n\in \omega }$ such that the function's graph is ${\displaystyle \Sigma _{n}}$-definable in ${\displaystyle (L_{\alpha },\in )}$.

Additional connections between recursion theory and α recursion theory can be drawn, although explicit definitions may not have yet been written to formalize them:

• The functions ${\displaystyle \Delta _{0}}$-definable in ${\displaystyle (L_{\alpha },\in )}$ play a role similar to those of the primitive recursive functions.

We say R is a reduction procedure if it is ${\displaystyle \alpha }$ recursively enumerable and every member of R is of the form ${\displaystyle \langle H,J,K\rangle }$ where H, J, K are all α-finite.

A is said to be α-recursive in B if there exist ${\displaystyle R_{0},R_{1}}$ reduction procedures such that:

${\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}$

${\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}$

If A is recursive in B this is written ${\displaystyle \scriptstyle A\leq _{\alpha }B}$. By this definition A is recursive in ${\displaystyle \scriptstyle \varnothing }$ (the empty set) if and only if A is recursive. However A being recursive in B is not equivalent to A being ${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$.

We say A is regular if ${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$ or in other words if every initial portion of A is α-finite.